/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-11-14
 * Time: 0:57
 */
public class Solution {
    public int count;
    public void mergeAndCount(int[]arr, int left,int right){
        if(left>=right){
            return ;
        }
        int mid=(left+right)>>1;
        int start1=left;
        int end1=mid;
        int start2=mid+1;
        int flag=start2;
        int end2=right;
        mergeAndCount(arr,start1,end1);
        mergeAndCount(arr,start2,end2);
        //排序时计算
        int index=0;
        int[] temp=new int[right-left+1];
        while(start1<=end1&&start2<=end2){
            //可以在start1右移时统计
            //也可在start2右移时统计
            if(arr[start1]<=arr[start2]){
                //注意这里加上等号
                temp[index++]=arr[start1++];
                count+=start2-flag;
            }else{
                temp[index++]=arr[start2++];
            }
        }
        while(start1<=end1){
            temp[index++]=arr[start1++];
            //这里注意如果是按照start2右移时统计则while循环时不需要在计算
            //因为用start2时,因为能产生的逆序对已经全部计算过了
            count+=start2-flag;
        }
        while(start2<=end2){
            temp[index++]=arr[start2++];
        }
        //拷贝回去
        for(int i=0;i<index;i++){
            arr[left+i]=temp[i];
        }
    }
    public int reversePairs(int[] nums) {
        mergeAndCount(nums,0,nums.length-1);
        return count;
    }
}